package com.zhhe.algorithm;

import com.zhhe.tree.BigHeap;

/*
 *Author:ZouHeng
 *Des:排序算法
 * 参考网址：https://www.cnblogs.com/onepixel/articles/7674659.html
 *Date:2020-08-21  16:10
 */
public class SortAlgorithm {
    public static void main(String[] args) {
//        int[] array = {1, 23, 4, 2, 54, 123, 5, 32, 5342, 56, 12, 34, 25};
        int[] array = {26,42,20,17,27,13,8,17,48};
        //        int[] result = bubbleSort(array);
        //        int[] result = simpleSelectSort(array);
        //        int[] array = {1, 6, 20, 3};
        //        int[] result = simpleInsertSort(array);
        //        int[] result = shellSort(array);
//        quickSort(array, 0, array.length - 1);
        int[] sortArr = heapSort(array);
        for (int item : sortArr) {
            System.out.print(item + "  ");
        }

    }


    /**
     * 冒泡排序
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    /**
     * 简单选择排序
     *
     * @param array
     * @return
     */
    public static int[] simpleSelectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int index = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[index]) {
                    index = j;
                }
            }
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
        return array;
    }

    /**
     * 简单插入排序
     *
     * @param array
     * @return
     */
    public static int[] simpleInsertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
        return array;
    }

    /**
     * 希尔排序
     *
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr) {
        //增量gap，并逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                while (j - gap >= 0 && arr[j] < arr[j - gap]) {
                    //插入排序采用交换法
                    swap(arr, j, j - gap);
                    j -= gap;
                }
            }
        }
        return arr;
    }

    /**
     * 快排
     * @param arr
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序
     *
     * @param low  低标志位，一般传0
     * @param high 高标志位，一般传数组长度-1
     * @return
     */
    private static void quickSort(int[] arr, int low, int high) {
        int i, j, index;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        index = arr[i]; // 用子表的第一个记录做基准
        while (i < j) { // 从表的两端交替向中间扫描
            while (i < j && arr[j] >= index){
                j--;
            }
            if (i < j){
                arr[i] = arr[j];// 用比基准小的记录替换低位记录
                i++;
            }

            while (i < j && arr[i] < index){
                i++;
            }
            // 用比基准大的记录替换高位记录
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = index;// 将基准数值替换回 a[i]
        quickSort(arr, low, i - 1); // 对低子表进行递归排序
        quickSort(arr, i + 1, high); // 对高子表进行递归排序
    }

    private void myQuickSOrt(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i, j, temp;
        i = low;
        j = high;
        temp = arr[i];
        while(i < j) {
            //从高位开始
            while (i < j && arr[j] >= temp) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            //低位
            while(i < j && arr[i] <= temp) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = temp;
        myQuickSOrt(arr, low, j - 1);
        myQuickSOrt(arr, i + 1, high);
    }

    /**
     * 堆排序
     *
     * @param array
     * @return
     */
    public static int[] heapSort(int[] array) {
        return BigHeap.BigHeapSort(array);
    }

    /**
     * 二路归并排序
     *
     * @param array
     * @return
     */
    public static int[] twoWayMergeSort(int[] array) {
        return null;
    }

    /**
     * 多路归并排序
     *
     * @param array
     * @return
     */
    public static int[] multiplexingMergeSort(int[] array) {
        return null;
    }

    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] countSort(int[] array) {
        return null;
    }

    /**
     * 桶排序
     *
     * @param array
     * @return
     */
    public static int[] bucketSort(int[] array) {
        return null;
    }

    /**
     * 基数排序
     *
     * @param array
     * @return
     */
    public static int[] radixSort(int[] array) {
        return null;
    }

    /**
     * 数组元素交换
     * @param arr 数组
     * @param a 元素a
     * @param b 元素b
     */
    public static void swap(int[] arr, int a, int b) {
        arr[a] = arr[a] + arr[b];
        arr[b] = arr[a] - arr[b];
        arr[a] = arr[a] - arr[b];
    }

}

















